#include <math.h>
#include <stdio.h>
#include <stdlib.h>
// 只能打印malloc的
void printArr(int* arr, int len) {
    printf("[");
    for (int i = 0; i < len; i++) {
        printf("%d ", arr[i]);
    }
    printf("]\n");
}

/**
 * 动态规划题
 */
int fib(int n) {
    if (n == 0) {
        return 0;
    }
    if (n == 1) {
        return 1;
    }
    int* arr = (int*)calloc(n + 1, 4);
    arr[1] = 1;
    for (int i = 2; i < n + 1; i++) {
        arr[i] = (arr[i - 1] + arr[i - 2]) % 1000000007;
    }
    return arr[n];
}
// 跳台阶
int numWays(int n) {
    int* arr = (int*)calloc(n + 2, 4);
    arr[1] = 1;
    for (int i = 2; i < n + 2; i++) {
        arr[i] = (arr[i - 1] + arr[i - 2]) % 1000000007;
    }
    return arr[n + 1];
}
// 股票最大利润
int maxProfit(int* prices, int pricesSize) {
    if (pricesSize == 0) {
        return 0;
    }
    if (pricesSize == 1) {
        return prices[0];
    }

    int* minArr = (int*)malloc(pricesSize * 4);
    minArr[0] = prices[0];
    int res = 0;
    for (int i = 1; i < pricesSize; i++) {
        minArr[i] = (int)fmin(minArr[i - 1], prices[i]);
        res = (int)fmax(res, prices[i] - minArr[i]);
    }
    return res;
}
// 最大子数组和
int maxSubArray(int* nums, int numsSize) {
    if (numsSize == 1) {
        return nums[0];
    }
    int* dp = (int*)malloc(numsSize * 4);
    dp[0] = nums[0];
    int res = dp[0];
    // dp[n] = arr[i] + dp[i - 1] < arr[i] ? nums[i] : dp[i - 1] + nums[i]
    for (int i = 1; i < numsSize; i++) {
        // 抛弃前面的 --> 这个至关重要，极其易错
        if (nums[i] + dp[i - 1] < nums[i]) {
            dp[i] = nums[i];
        }
        // 还要前面的
        else {
            dp[i] = dp[i - 1] + nums[i];
        }
        res = (int)fmax(res, dp[i]);
    }
    // 注意这个返回的不应该是dp的最后一项，而是记录维护一个max(dp)
    return res;
}
// 剑指 Offer 47. 礼物的最大价值
// int maxValue(int** grid, int gridSize, int* gridColSize) {
//     print("111\n");
//     int** dp = (int**)malloc(sizeof(int*) * gridSize + 1);
//     for (int i = 0; i < *gridColSize; i++) {
//         dp[i] = (int*)calloc(*gridColSize + 1, 4);
//     }
//     print("222\n");
//     for (int y = 0; y < gridSize; y++) {
//         for (int x = 0; x < *gridColSize; x++) {
//             dp[y + 1][x + 1] = (int)fmax(dp[y + 1][x], dp[y][x + 1]) + grid[y][x];
//         }
//     }
//     print("333\n");
//     return dp[gridSize][*gridColSize];
// }

int translateNum(int num) {
    if (num < 10) {
        return 1;
    }
    int arr[10] = {};
    int index = 0;
    while (num != 0) {
        arr[index] = num % 10;
        num /= 10;
        index++;
    }
    // index 最终表示len
    // reverse
    int nums[10] = {};
    for (int i = index - 1; i >= 0; i--) {
        nums[index - i - 1] = arr[i];
    }
    int dp[10] = {1};
    dp[1] = nums[0] * 10 + nums[1] > 25 ? 1 : 2;

    for (int i = 2; i < index; i++) {
        dp[i] = dp[i - 1];
        if (nums[i - 1] * 10 + nums[i] <= 25 && nums[i - 1] != 0) {
            dp[i] += dp[i - 2];
        }
    }
    // printf("%d %d %d\n", nums[0], nums[1], nums[2]);
    return dp[index - 1];
}
int* countBits(int n, int* returnSize) {
    *returnSize = n + 1;
    int* arr = (int*)malloc(4 * (n + 1));
    for (int i = 0; i <= n; i++) {
        int count = 0;

        arr[i] = count;
    }
    return arr;
}

struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
};

int RES = -99999;

void dpDFS(struct TreeNode* curNode) {
    if (curNode == NULL) {
        return;
    }
    dpDFS(curNode->left);
    dpDFS(curNode->right);
    // 修改这个节点
    int leftVal = curNode->left == NULL ? 0 : curNode->left->val;
    int rightVal = curNode->right == NULL ? 0 : curNode->right->val;
    int thisVal = curNode->val;
    curNode->val = (int)fmax(
        (int)fmax(thisVal + rightVal + leftVal, thisVal),
        (int)fmax(thisVal + rightVal, thisVal + leftVal));

    RES = (int)fmax(RES, curNode->val);
}
int maxPathSum(struct TreeNode* root) {
    return RES;
}

int minCostClimbingStairs(int* cost, int costSize) {
    int* dp = (int*)malloc(4 * (costSize));
    dp[0] = cost[0];
    dp[1] = cost[1];
    for (int i = 2; i < costSize; i++) {
        dp[i] = cost[i] + (int)fmin(dp[i - 1], dp[i - 2]);
    }
    return (int)fmin(dp[costSize - 1], dp[costSize - 2]);
}

int main() {
    return 0;
}
